# 使用 trie
# 超 88% 的用户
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.hasEmpty = False

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        wlen = len(word)
        if wlen == 0:
            self.hasEmpty = True
            return

        curr = self.root
        for index, letter in enumerate(word):
            if letter in curr:
                if index == wlen - 1:
                    curr[letter][1] = True
                    return
                else:
                    curr = curr[letter][0]
            else:
                node = [{}, index == wlen - 1]
                curr[letter] = node
                curr = node[0]

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        return self.searchI(self.root, 0, word)


    def searchI(self, letterMap, index, word):
        wlen = len(word)
        letter = word[index]
        if len(letterMap) == 0:
            return False
        if wlen - 1 == index:
            if letter == '.':
                for kletter in letterMap.keys():
                    if letterMap[kletter][1]:
                        return True
                return False
            else:
                if letter not in letterMap:
                    return False
                if not letterMap[letter][1]:
                    return False
                return True
        else:
            if letter == '.':
                for kletter in letterMap.keys():
                    if self.searchI(letterMap[kletter][0], index + 1, word):
                        return True
                return False
            else:
                if letter not in letterMap:
                    return False
                return self.searchI(letterMap[letter][0], index + 1, word)



# Your WordDictionary object will be instantiated and called as such:
obj = WordDictionary()
obj.addWord("at")
obj.addWord("and")
obj.addWord("an")
obj.addWord("add")
print(obj.search("a")) # false
print(obj.search(".at")) # false

obj.addWord("bat")
print(obj.search(".at"))  # true
print(obj.search("an."))  # true
print(obj.search("a.d.")) # false
print(obj.search("b."))   # false
print(obj.search("a.d"))  # true
print(obj.search("."))    # false